/* 已知满二叉树先序序列存在于数组中，设计算法将其变成后序序列 */

#include <iostream>
using namespace std;

// 先序遍历 -> 后序遍历
void change(char pre[], int L1, int R1, char post[], int L2, int R2)
{
  // 如果起始索引和结束索引均符合要求
  if (L1 <= R1 && L2 <= R2)
  {
    // 根结点对应位置
    post[R2] = pre[L1];
    
    // 左子树，先序遍历 -> 后序遍历
    change(pre, L1 + 1, (L1 + R1 + 1) / 2, post, L2, (L2 + R2 - 1) / 2);
    
    // 右子树，先序遍历 -> 后序遍历
    change(pre, (L1 + R1 + 1) / 2 + 1, R1, post, (L2 + R2 - 1) / 2 + 1, R2 - 1);
  }
}

// 后序遍历 -> 先序遍历
void change1(char post[], int L1, int R1, char pre[], int L2, int R2)
{
  // 如果起始索引和结束索引均符合要求
  if (L1 <= R1 && L2 <= R2)
  {
    // 根结点对应位置
    pre[L2] = post[R1];
    
    // 左子树，后序遍历 -> 先序遍历
    change1(post, L1, (L1 + R1 - 1) / 2, pre, L2 + 1, (L2 + R2 + 1) / 2);
    
    // 右子树，后序遍历 -> 先序遍历
    change1(post, (L1 + R1 - 1) / 2 + 1, R1 - 1, pre, (L2 + R2 + 1) / 2 + 1, R2);
  }
}

// 先序遍历 -> 中序遍历
void change2(char pre[], int L1, int R1, char mid[], int L2, int R2)
{
  // 如果起始索引和结束索引均符合要求
  if (L1 <= R1 && L2 <= R2)
  {
    // 根结点的对应位置
    mid[(L2+R2)/2] = pre[L1];
    
    // 左子树，先序遍历 -> 中序遍历
    change2(pre, L1+1, (L1 + R1 +1) / 2, mid, L2 , (L2 + R2) / 2-1);
    
    // 右子树，先序遍历 -> 中序遍历
    change2(pre, (L1 + R1 +1) / 2 + 1, R1 , mid, (L2 + R2 + 1) / 2 + 1, R2);
  }
}


int main()
{
  // 先序遍历的结果
  char pre[8] = "abdecfg";
  char mid[8] = "";
  
  // 已知先序遍历，求中序遍历结果
  change2(pre, 0, 6, mid, 0, 6);
  
  // 打印中序遍历结果
  int i = 0;
  while (mid[i] != '\0')
  {
    cout << mid[i];
    ++i;
  }
  return 0;
}
